/**
 * @program: LeetCode
 * @description: LeetCode : 213. 打家劫舍 II
 * @author: WXY
 * @create: 2023-01-07 20:03
 * @Version 1.0
 **/
public class Num213_rob {
    //将环拆成两个数组
    // 0,....n - 1,
    // 1......n
    public static int rob(int[] arr) {
        if (arr.length == 1) return arr[0];
//        int[] arr1 = Arrays.copyOfRange(arr, 0, arr.length - 1);
//        int[] arr2 = Arrays.copyOfRange(arr, 1, arr.length);
//        int max1 = getMaxAmount(arr1);
//        int max2 = getMaxAmount(arr2);
        int max1 = getMaxAmount(arr, 0, arr.length - 2);
        int max2 = getMaxAmount(arr, 1, arr.length - 1);
        return Math.max(max1, max2);
    }

    private static int getMaxAmount(int[] arr) {
        if (arr.length == 1) return arr[0];
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[arr.length - 1];
    }

    private static int getMaxAmount(int[] arr, int start, int end) {
        if (start == end) return arr[start];
        int[] dp = new int[arr.length];
        dp[start] = arr[start];
        dp[start + 1] = Math.max(arr[start], arr[start + 1]);
        for (int i = start + 2; i <= end ; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[end];
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,1};
        int rob = rob(arr);
        System.out.println(rob);
    }
}
